package cn.edu.zufe.mjt.binary;

import java.util.Arrays;

/**
 * 二分答案问题：购物车的降级策略
 * 问题描述：在一个购物APP中，有一个核心购物系统，它的接口被 N 个客户端调用。这些客户端负责处理来自不同渠道的交易请求，并将这些请求发送给核心购物系统。
 * 每个客户端有不同的调用量 R=「R1,R2,…,Rn」，表示在一定时间内，这个客户端向核心购物系统发送的交易请求的数量。核心购物系统必须能够及时响应所有的请求，以确保交易顺利进行。
 * 然而，最近核心购物系统出现了集群故障，导致交易请求的处理速度变慢。为了避免系统崩溃，必须临时降级并限制调用量。
 * 具体而言，核心购物系统能接受的最大调用量为 cnt，如果客户端发送的请求总量超过 cnt，则必须限制一些系统的请求数量，以确保核心购物系统不会超负荷工作。
 * 现在需要一个降级规则，来限制客户端的请求数量。
 * 规则如下:如果 sum(R1,R2,…,Rn)小于等于 cnt ，则全部可以正常调用，返回 -1;
 * 如果 sum(R1,R2,…,Rn)大于 cnt，则必须设定一个阈值 value，如果某个客户端发起的调用量超过 value则该客户端的请求数量必须限制为 value。
 * 其余未达到 value 的系统可以正常发起调用。要求求出最大的value(value 可以为0)。
 * 为了保证交易的顺利进行，必须保证客户端请求的数量不会超过核心购物系统的最大调用量，同时最大的 value 要尽可能的大。需要高效地解决这个问题，以确保购物系统的高效性。
 * 输入描述
 * 第一行:每个客户端的调用量(整型数组)第二行:核心购物系统的最大调用量 0 <R.length ≤ 10^5, 0≤ R[i]≤10^5 , 0 ≤cnt ≤ 10^9
 * 输出描述
 * 调用量的阈值 value
 */
public class BinaryAnswerQuestions {
    public static void main(String[] args) {
        int[] clientCall = {1, 4, 2, 5, 5, 1, 6};
        int cnt = 13;

        // 1+4+2+5+5+1+6=24 > cnt = 13
        // value = 2 1+2+2+2+2+1+2=12 < cnt=13
        // value = 3 1+3+2+3+3+1+3=16 > cnt=13
        // value = 4 1+4+2+4+4+1+4=20 > cnt=13
        // value = 5 1+4+2+5+5+1+5=23 > cnt=13
        // value ≥ 6 1+4+2+5+5+1+6=24 > cnt=13
        // 答案具有单调性，所以考点就叫二分答案
        int value = getMaxCallValue(clientCall, cnt);
        System.out.println(value);

    }

    /**
     * 答案具有单调性：
     * ①建立value与sum之间的关系
     * ②转换为数组问题:value看作数组下标，sum看作数组元素
     * ③问题本质:寻找 数组中 小于等于cnt的最大值 对应的下标
     * ④应用二分四部曲
     */
    public static int getMaxCallValue(int[] R, int cnt) {
        int l = 0;
        int max = Arrays.stream(R).max().orElse(Integer.MAX_VALUE);
        int r = max;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int sum = getSum(R, mid);
            if (sum <= cnt) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (r == max) {
            return -1;
        }
        return r;
    }

    private static int getSum(int[] arr, int value) {
        int sum = 0;
        for (int i : arr) {
            sum+=Math.min(i,value);
        }
        return sum;
    }
}
